package seqlist.LeetCode;
//206. 反转链表
//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

/**
 * 思路一：头插法。因为题目没有要求原地翻转，最简单的方法就可以创建一个新链表
 * 用一个虚拟头节点，再用一个指针去遍历原链表，遇到一个节点就new一个一模一样值
 * 的节点用来头插入虚拟头节点。这样虚拟头节点得到的链表就是反过来了的
 */

/*

public class Num206_reverseList {
    public ListNode reverseList(ListNode head) {

        //当链表为空或者 只有一个是时候，就不需要翻转链表了
        if(head == null || head.next == null){
            return head;
        }

        ListNode dummyHead = new ListNode();
        while(head != null){
            ListNode node = new ListNode(head.val);
            node.next = dummyHead.next;
            dummyHead.next = node;
            head = head.next;
        }
        return dummyHead.next;
    }
}

 */

/**
 * 思路二：这个就是迭代法。 原地移动链表。 所谓的链表反转就是相当于 原来的 1 -》 2 变成了 2 -》 1
 * 把每个节点的 原来的 所指向的方法反一下就可以了。
 * 用 两个指针 prve 和 cur 来实现相反，再加上一个指针 next记录下
 * 一个节点的地址，保持三指针的移动。
 * 注释：当 cur走到null的时候， 你会发现 此时的prve正好在 链表末尾上，
 * 到时候直接返回 prve就可以了
 */


/**
 * 思路二：迭代法。可以遇到一个节点就让那个节点进行头插步骤。但需要一个不动的前驱。
 * 所以创建一个虚拟头节点。再用prve和node两个节点，每遇到一个节点，prve就让他保存
 * 的地址指向下一个的下一个，遇到null为截止。node就是prve.next地址节点进行头插。
 * 然后每次都更新dummyHead链接的地址
 */

/*

public class Num206_reverseList {
    public ListNode reverseList(ListNode head) {

        //当链表为空或者 只有一个是时候，就不需要翻转链表了
        if(head == null || head.next == null){
            return head;
        }
        //此时链表至少有两个节点
        ListNode dummyHead = new ListNode();//虚拟前驱
        ListNode prve = head;//因为要让第一个节点指向null
        dummyHead.next = prve;//连接一下
        while(prve.next != null){
            ListNode node  = prve.next;
            prve.next = node.next;//跳过头插节点
            node.next = dummyHead.next;//进行头插
            dummyHead.next = node;//更新新的头节点地址
        }
        return dummyHead.next;
    }
}

 */

/**    //这个就是迭代法
 * 思路2：原地移动链表。 所谓的链表反转就是相当于 原来的 1 -》 2 变成了 2 -》 1
 * 把每个节点的 原来的 所指向的方法反一下就可以了。
 * 用 两个指针 prve 和 cur 来实现相反，再加上一个指针 next记录下
 * 一个节点的地址，保持三指针的移动。
 * 注释：当 cur走到null的时候， 你会发现 此时的prve正好在 链表末尾上，
 * 到时候直接返回 prve就可以了
 */

/*

class Solution {
    public ListNode reverseList(ListNode head) {

        ListNode prve = null;//因为要让第一个节点指向null
        ListNode cur = head;

        while(cur != null){
            ListNode next = cur.next;//记录下一个节点的地址，不然等会反转就找不到了
            cur.next = prve;
            prve = cur;//移动一位
            cur = next;//移位移位
        }
        return prve;

    }
}

*/

/**
 * 思路三：运用递归法来解决。 可以这么拆分：我们每次都知道头节点，所以我们也只
 * 处理头节点的情况， 把 head.next交给子方法去解决后用 prve 接受一下返回地址，
 * 因为它就是接下来新链表的头节点了
 * 然后我们手动把头节点移动到链表末尾
 * 注释：记得先保存链表的第二个节点地址，因为等会交给子方法翻转后它就是末尾了。
 */

public class Num206_reverseList {

    public ListNode reverseList(ListNode head) {

        //什么情况下可以不用拆分，或者可以直接知道答案？
        if(head == null || head.next == null){
            return head;
        }
        //到这说明至少有两个节点了
        ListNode node = head.next;//保存地址，方便等会头节点插它后面
        ListNode prve = reverseList(head.next);//这就是新链表的头节点，保存下来
        node.next = head;
        head.next = null;//不置空 会 回环

        return prve;
    }
}